public class code01 {
//    力扣 150 从前序和中序遍历构造二叉树
    // 这道题目的要求是要通过先序遍历和中序遍历的结果集将二叉树构造出来
    // 针对 二叉树的问题，采用递归的策略来解决

    public HashMap<Integer, Integer> map;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 先序遍历和中序遍历在树中是有关联关系的
        // 通过使用 Map 将当前中序遍历的结果与其数组下标之间进行绑定，这样可以快速的定位到根节点
        map = new HashMap<>();

        // 首先获取中序遍历的长度
        int n = inorder.length;
        for(int i = 0; i < n; i++) {
            // 这里是将 中序遍历 中的元素作为 key
            // key 映射到的下标位置就和 先序遍历 中的结果有关联关系
            map.put(inorder[i], i);
        }
        // 构造一个方法，专门实现对于 二叉树 的构建
        TreeNode re = Build(preorder, 0, n - 1, inorder, 0, n - 1);
        return re;
    }


    // 这个方法中需要接受到的参数包含：
    // 先序遍历结果集、中序遍历结果集
    // 先序遍历数组的长度
    // 中序遍历数组长度
    public TreeNode Build(int[] preorder, int p_left, int p_right, int[] inorder, int i_left, int i_right) {
        if(p_left > p_right) {
            return null;
        }

        // 首先记录一下先序遍历的第一个节点
        // 先序遍历的第一个节点是根节点
        int p_root = p_left;

        // 根据先序遍历中的节点数据查找中序遍历中该元素对应的下标位置
        int i_root = map.get(preorder[p_root]);

        // 建立根节点
        TreeNode root = new TreeNode(preorder[p_root]);

        // 获取左子树上的元素
        // 左子树上的元素也就是 中序遍历 中间的根节点左侧对应的元素
        int treeLeft = i_root - i_left;

        // 先来通过递归构造左子树
        // 在先序遍历中，从 左边界+1(左边界第一个元素是 根 节点) 开始 到 treeLeft 的长度的元素
        // 在中序遍历中，从 左边界 开始到 根节点定位 - 1 的元素
        // 这两部分的元素都为左子树上的节点
        root.left = Build(preorder, p_left + 1, p_left + treeLeft, inorder, i_left, i_root - 1);

        // 构造右子树
        // 先序遍历中 左边界 + 1 + treeLeft 开始 到 右边界
        // 中序遍历 根节点 + 1 到 右边界
        // 这两部分元素都为右子树上的节点
        root.right = Build(preorder, p_left + 1 + treeLeft, p_right, inorder, i_root + 1, i_right);

        return root;
    }
}
